package leetcode.editor.cn.q1_300.q150;

import java.util.Arrays;

/**
 * 自己的所有思路都做不到 在线性时间复杂度和空间复杂度的条件下解决此问题。
 * 只能看答案了。。。结果答案也是排序，好吧，我快把桶排序给忘完了
 *
 * @author qidi
 * @date 2022-01-24 09:52:39
 */
class Q0164_MaximumGap {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int maximumGap(int[] nums) {
            int n = nums.length;
            if (n < 2) return 0;
            int min = Integer.MAX_VALUE;
            int max = 0;

            for (int num : nums) {
                min = Math.min(min, num);
                max = Math.max(max, num);
            }
            int len = Math.max(1, (max - min) / (n - 1));

            int bucketSize = (max - min) / len + 1;

            int[][] bucket = new int[bucketSize][2];
            for (int i = 0; i < bucketSize; i++) {
                Arrays.fill(bucket[i], -1);
            }

            for (int num : nums) {
                int i = (num - min) / len;
                if (bucket[i][0] == -1) {
                    bucket[i][0] = bucket[i][1] = num;
                } else {
                    bucket[i][0] = Math.min(bucket[i][0], num);
                    bucket[i][1] = Math.max(bucket[i][1], num);
                }
            }

            int ans = 0;
            int pre = -1;
            for (int i = 0; i < bucketSize; i++) {
                if (bucket[i][0] == -1) continue;

                if (pre != -1) {
                    ans = Math.max(ans, bucket[i][0] - bucket[pre][1]);
                }
                pre = i;
            }
            return ans;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0164_MaximumGap().new Solution();
        System.out.println(solution.maximumGap(new int[]{3, 6, 9, 1}));
    }
}